//
//  Problem29.swift
//  TestProject 29. 两数相除
//
//  Created by 武侠 on 2020/8/20.
//  Copyright © 2020 zhulong. All rights reserved.
//

import UIKit

/*
 29. 两数相除
 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 返回被除数 dividend 除以除数 divisor 得到的商。
 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2


 示例 1:
 输入: dividend = 10, divisor = 3
 输出: 3
 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
 
 示例 2:
 输入: dividend = 7, divisor = -3
 输出: -2
 解释: 7/-3 = truncate(-2.33333..) = -2
  
 提示：
 被除数和除数均为 32 位有符号整数。
 除数不为 0。
 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,  231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
 */
@objcMembers class Problem29: NSObject {
    @objc func solution() {
        var s:Int = 10
        print(divideW(10, 3))
        print(divideW(7, -3))
        print(divideW(-2147483648, -1))
    }
    
    // 一：2分分解
    // 可以简单概括为： 60/8 = (60-32)/8 + 4 = (60-32-16)/8 + 2 + 4 = 1 + 2 + 4 = 7
    // 1: 8 + 8 = 16 < 60       n = 1 + 1 = 2
    // 2: 16 + 16 = 32 < 60     n = 2 + 2 = 4
    // 3: 32 + 32 = 64 > 60, 找到第一个>60的数字
    // 4: n(4) + (60 - 32)/4 = 4 + 28 / 8   // 递归
    @objc func divide(_ dividend: Int, _ divisor: Int) -> Int {
        if dividend == 0 {
            return 0
        }
        if divisor == 1 {
            return dividend
        }
        
        // 这一步是从网友那得到的
        if(divisor == -1) {
            if(dividend > Int32.min) {
                return -dividend;       // 只要不是最小的那个整数，都是直接返回相反数就好啦
            } else {
                return Int(Int32.max);  // 是最小的那个，那就返回最大的整数啦, 如果返回-dividend就越界了。
            }
        }
        
        // 判断负数
        var flag = 1
        if (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) {
            flag = -1
        }
        // 全部转换成正数
        let sa = dividend < 0 ? -dividend : dividend
        let sb = divisor < 0 ? -divisor : divisor
        
        // 进行核心的递归计算
        let re = div(sa, sb)
        return flag == -1 ? -re : re
    }
    
    // 已经确保2个参数都是>0
    @objc func div(_ dividend: Int, _ divisor: Int) -> Int {
        if dividend < divisor {
            return 0
        }
        
        // 定一个：个数
        var n = 1
        var tb = divisor        // 每次自加，变相的2分法
        while (tb + tb) < dividend {
            n += n
            tb += tb
        }
        
        return n + div(dividend - tb, divisor)
    }
    
    // 二：采用位移的方式 >> 就是 * 2
    // 采用2层循环，不用递归
    @objc func divideW(_ dividend: Int, _ divisor: Int) -> Int {
        if dividend == 0 {
            return 0
        }
        if divisor == 1 {
            return dividend
        }
        
        // 这一步是从网友那得到的
        if(divisor == -1) {
            if(dividend > Int32.min) {
                return -dividend;       // 只要不是最小的那个整数，都是直接返回相反数就好啦
            } else {
                return Int(Int32.max);  // 是最小的那个，那就返回最大的整数啦, 如果返回-dividend就越界了。
            }
        }
        
        // 判断负数
        var flag = 1
        if (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0) {
            flag = -1
        }
        // 全部转换成正数
        var sa = dividend < 0 ? -dividend : dividend
        let sb = divisor < 0 ? -divisor : divisor
        
        // 只要 小于，说明还可以相除
        var result = 0
        while sa >= sb {
            var tsb = sb    // 用来位移
            var n = 1       // 用来计算个数
            while (sa-tsb) > tsb {
                tsb = tsb << 1
                n = n << 1
            }

            
            sa -= tsb
            result += n
        }
        
        return flag == -1 ? -result : result
    }
}
